// 从0开始
template<class T>
struct Heap {
	vector<T> heap;
	int siz;

	Heap() : siz(0) {}
	Heap(const vector<T> &heap_) : heap(heap_), siz(heap_.size()) {
		buildHeap();
	}

	void buildHeap() {
		for (int i = siz; i >= 0; i--) {
			down(i);
		}
	}

	void down(int u) {
		int rt = u, ls = (u << 1) + 1, rs = (u << 1) + 2;
		if (ls < siz && heap[ls] < heap[rt]) {
			rt = ls;
		}
		if (rs < siz && heap[rs] < heap[rt]) {
			rt = rs;
		}
		if (u != rt) {
			swap(heap[u], heap[rt]);
			down(rt);
		}
	}

	void up(int u) {
		int f = (u - 1) >> 1;
		while (u >= 1 && heap[u] < heap[f]) {
			swap(heap[u], heap[f]);
			u = f;
			f = (u - 1) >> 1;
		}
	}

	void push(const T& u) {
		heap.push_back(u);
		up(siz++);
	}

	bool empty() {
		return !siz;
	}

	int size() {
		return siz;
	}

	T top() {
		assert(siz);
		return heap[0];
	}

	void pop() {
		if (!siz) {
			return;
		}
		heap[0] = heap.back();
		siz--;
		heap.pop_back();
		down(0);
	}
};